#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = (1<<12)+10;
const int M = (1<<16)+10;
const int OP = 2.2e6+10;
const int BL = (1<<8)+10;
int tot,c[OP],d[OP],q,n,a[N],pos[N],ans[M];

int merge(int x,int y){
	if(!x || !y) return x + y;
	return c[++tot] = x,d[tot] = y,tot;
}

struct BLOCK{
	vector<vector<int> >id; vector<int> val;
	void init(int x){val.resize(x); id.resize(x); for(int i = 0;i < x;i++) id[i].resize(x-i);}
	BLOCK(int x = -1){if(~x)init(1),val[0] = pos[x],id[0][0] = pos[x]+1;}
	int ask(int l,int r){
		if(l > val.back() || r < val.front()) return 0;
		int x = lower_bound(val.begin(),val.end(),l) - val.begin();
		int y = upper_bound(val.begin(),val.end(),r) - val.begin() - 1;
		if(x > y) return 0; else return id[x][y-x];
	}
	friend BLOCK operator + (BLOCK a,BLOCK b){
		BLOCK ans; ans.init(a.val.size()+b.val.size());
		merge(a.val.begin(),a.val.end(),b.val.begin(),b.val.end(),ans.val.begin());
		for(int i = 0;i < ans.val.size();i++)
			for(int j = i;j < ans.val.size();j++)
				ans.id[i][j-i] = merge(a.ask(ans.val[i],ans.val[j]),b.ask(ans.val[i],ans.val[j]));
		return ans;
	}
}B[N];

BLOCK solve(int l,int r){
	if(l == r) return BLOCK(l); int mid = l+r>>1;
	return solve(l,mid) + solve(mid+1,r);
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in;q = in; int blo = sqrt(q); tot = n;
	for(int i = 0;i < n;i++) a[i] = in-1,pos[a[i]] = i;
	for(int i = 0;i <= (n-1)/blo;i++) B[i] = solve(i*blo,min(n-1,(i+1)*blo-1));
	for(int i = 0;i < q;i++){
		int l = in-1,r = in-1;
		for(int j = 0;j <= (n-1)/blo;j++) ans[i] = merge(ans[i],B[j].ask(l,r));
	}
	printf("%d\n",tot); for(int i = n+1;i <= tot;i++) printf("%d %d\n",c[i],d[i]);
	for(int i = 0;i < q;i++) printf("%d%c",ans[i]," \n"[i==q-1]);
	return 0;
}

